Memoization এবং Tabulation Techniques গাইড ও নোট

Memoization এবং Tabulation হলো Dynamic Programming (ডাইনামিক প্রোগ্রামিং) এর দুটি প্রধান কৌশল যা সাধারণত recursive algorithms বা পুনরাবৃত্তি অ্যালগরিদমের দক্ষতা বাড়াতে ব্যবহৃত হয়। এই কৌশলগুলি একে অপরের বিপরীত হলেও তাদের লক্ষ্য একই: গণনা করা ফলাফলগুলো সংরক্ষণ করা যাতে পুনরায় একই ফলাফল গণনা না করতে হয়, যা পারফরম্যান্স উন্নত করে।

Memoization

Memoization হলো একটি উপায় যা top-down পদ্ধতিতে কাজ করে। এটি পুনরাবৃত্তি ফাংশনগুলিতে ফলাফলগুলো সংরক্ষণ করে যাতে পরবর্তীতে সেই ফলাফলগুলো পুনরায় গণনা করতে না হয়।

Tabulation

Tabulation হলো একটি bottom-up পদ্ধতি, যেখানে আপনি ছোট ছোট উপসমস্যাগুলির সমাধান করতে করতে বড় সমস্যার সমাধান করেন এবং একে একে সকল ফলাফল একটি টেবিল (array বা 2D array) এ সংরক্ষণ করেন।

১. Memoization (Top-Down)

Memoization হল একটি রিকার্সিভ কৌশল যা শুধুমাত্র প্রয়োজনীয় ফলাফল গুলি সংরক্ষণ করে। যখন একই সমস্যার জন্য পুনরায় গণনা করার প্রয়োজন হয় না, তখন পূর্বের ফলাফল ব্যবহার করা হয়।

উদাহরণ: Fibonacci Sequence - Memoization

ফিবোনাচ্চি সিকোয়েন্সের একটি সহজ উদাহরণ যেখানে আমরা Memoization ব্যবহার করে ফিবোনাচ্চি সিকোয়েন্স বের করার চেষ্টা করব।

import java.util.HashMap;

public class FibonacciMemoization {
    // HashMap ব্যবহার করে memoization সংরক্ষণ করা
    private HashMap<Integer, Integer> memo = new HashMap<>();

    // ফিবোনাচ্চি সিকোয়েন্সের জন্য মেমোইজড ফাংশন
    public int fibonacci(int n) {
        // যদি ফলাফল মেমোতে থাকে, তাহলে সোজা রিটার্ন করা
        if (memo.containsKey(n)) {
            return memo.get(n);
        }

        // বেস কেস
        if (n <= 1) {
            return n;
        }

        // Fibonacci সিকোয়েন্সের মান বের করা
        int result = fibonacci(n - 1) + fibonacci(n - 2);

        // ফলাফল মেমোতে সংরক্ষণ করা
        memo.put(n, result);

        return result;
    }

    public static void main(String[] args) {
        FibonacciMemoization fib = new FibonacciMemoization();
        int n = 10;
        System.out.println("Fibonacci of " + n + " is " + fib.fibonacci(n));
    }
}

ব্যাখ্যা:

• Memoization দ্বারা fibonacci ফাংশনে পূর্বে গণনা করা মানগুলো সংরক্ষণ করা হয় memo হ্যাশম্যাপে।
• প্রতিবার যখন একি মানের জন্য পুনরাবৃত্তি করা হয়, তখন Memoization সেই মানের জন্য পূর্বের ফলাফল সরাসরি রিটার্ন করে, ফলে গুণগতভাবে অপ্টিমাইজড করা হয়।

আউটপুট:

Fibonacci of 10 is 55

২. Tabulation (Bottom-Up)

Tabulation হল একটি bottom-up পদ্ধতি যেখানে আপনি ছোট ছোট সাবপ্রব্লেমগুলির জন্য ফলাফল একে একে গণনা করে একটি টেবিল বা অ্যারে ব্যবহার করে সেগুলিকে সংরক্ষণ করেন এবং পরে সেগুলিকে একত্রিত করে মূল সমস্যার সমাধান বের করেন।

উদাহরণ: Fibonacci Sequence - Tabulation

এখন, ফিবোনাচ্চি সিকোয়েন্সে Tabulation ব্যবহার করে সমাধান করা।

public class FibonacciTabulation {

    public int fibonacci(int n) {
        // Base cases for 0 and 1
        if (n <= 1) {
            return n;
        }

        // Tabulation: একটি অ্যারে তৈরি করা যা ফিবোনাচ্চি মান সংরক্ষণ করবে
        int[] dp = new int[n + 1];

        // বেস কেস
        dp[0] = 0;
        dp[1] = 1;

        // সিকোয়েন্সের মান গণনা করা
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];  // Fibonacci relation
        }

        return dp[n];
    }

    public static void main(String[] args) {
        FibonacciTabulation fib = new FibonacciTabulation();
        int n = 10;
        System.out.println("Fibonacci of " + n + " is " + fib.fibonacci(n));
    }
}

ব্যাখ্যা:

• এখানে Tabulation ব্যবহার করা হয়েছে যাতে ফলাফলগুলো একটি অ্যারে dp তে সংরক্ষিত হয়।
• আমরা প্রথমে বেস কেস নির্ধারণ করি (যেমন dp[0] = 0 এবং dp[1] = 1) এবং তারপর বাকী মানগুলি বটম-আপ পদ্ধতিতে গণনা করি।

আউটপুট:

Fibonacci of 10 is 55

Memoization vs Tabulation

1. Memoization (Top-Down):
   • Recursion ব্যবহার করে।
   • যতক্ষন না কোন সাবপ্রব্লেম প্রয়োজন হয় ততক্ষন কোন গণনা করা হয় না।
   • মেমোরি খরচ একটু বেশি হতে পারে (স্ট্যাক মেমরি) কারণ এটি রিকার্সিভ ফাংশন ব্যবহার করে।
2. Tabulation (Bottom-Up):
   • Iterative পদ্ধতি ব্যবহার করে, কোনো রিকার্সন নেই।
   • সমস্ত সাবপ্রব্লেমের ফলাফল একটি টেবিল (অথবা অ্যারে) এ সংরক্ষিত হয়।
   • মেমোরি ব্যবহারে একটু কম, কারণ এটি স্ট্যাক ব্যবহার করে না।

সারাংশ

Memoization এবং Tabulation হলো Dynamic Programming এর দুটি মৌলিক কৌশল যা পুনরাবৃত্তি অ্যালগরিদমগুলির কার্যকারিতা উন্নত করতে সহায়তা করে।

• Memoization: Top-Down পদ্ধতি, যেখানে আপনি রিকার্সিভ পদ্ধতিতে সাবপ্রব্লেমের ফলাফল সংরক্ষণ করেন।
• Tabulation: Bottom-Up পদ্ধতি, যেখানে আপনি একে একে সব সাবপ্রব্লেম সমাধান করে একটি টেবিল তৈরি করেন।

এই কৌশলগুলির মাধ্যমে আমরা একই সাবপ্রব্লেম পুনরায় গণনা থেকে বাঁচাতে পারি এবং সময়ের দক্ষতা বৃদ্ধি করতে পারি।